/*
Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
*/

class Solution {
public:
    int minCut(string s) {
        if (!s.length()) return 0;
        int mincut = INT_MAX;
        vector<int> cuts(s.length(), INT_MAX);
        vector<vector <bool>> P;
        // initialize P matrix to all false
        P.resize(s.length());
        for (int i = 0; i < P.size(); i++) P[i].resize(s.length(), false);          
        for (int i = 0; i < P.size(); i++) P[i][i] = true;                          // single char
        for (int i = 0; i < P.size()-1; i++) {if (s[i] == s[i+1]) P[i][i+1] = true;}// double chars
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                if (!P[j][i]) P[j][i] = (s[j] == s[i] && P[j+1][i-1]);
                if (P[j][i]) {
                    // palindrome substrinPg
                    int cut = (j==0)?0:(1+cuts[j-1]);
                    if (cut < cuts[i]) cuts[i] = cut;
                }
            }
        }
        return cuts[s.length()-1];
    }
};
